Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high standard accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of standard learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

Neural Information Processing Systems http://nips.cc/

Weshowaseparation result: on one hand, if the query radiusλis strictly smaller than the adversary's perturbation budgetρ, then distribution-free robust learning is impossible for a widevarietyofconcept classes; ontheotherhand,thesettingλ=ρallowsusto develop robust ERM algorithms.

Neural Information Processing Systems http://nips.cc/

This paper addresses the question of learning structured distributions from batches when a constant fraction of the batches might be corrupted. This problem has been of considerable recent interest. This paper studies the setting where the underlying distribution has additional structure (namely, piece polynomial density function), in which case more sample efficient algorithms are possible. This paper develops sample and computationally efficient algorithms for such settings. The reviewers were convinced that this paper makes important technical contributions in extending recent work on this problem to the structured setting.

We establish a new model-agnostic optimization framework for out-of-distribution generalization via multicalibration, a criterion that ensures a predictor is calibrated across a family of overlapping groups. Multicalibration is shown to be associated with robustness of statistical inference under covariate shift. We further establish a link between multicalibration and robustness for prediction tasks both under and beyond covariate shift. We accomplish this by extending multicalibration to incorporate grouping functions that consider covariates and labels jointly. This leads to an equivalence of the extended multicalibration and invariance, an objective for robust learning in existence of concept shift. We show a linear structure of the grouping function class spanned by density ratios, resulting in a unifying framework for robust learning by designing specific grouping functions. We propose MC-Pseudolabel, a post-processing algorithm to achieve both extended multicalibration and out-of-distribution generalization. The algorithm, with lightweight hyperparameters and optimization through a series of supervised regression steps, achieves superior performance on real-world datasets with distribution shift.